home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / SET.C < prev    next >
C/C++ Source or Header  |  1992-09-24  |  20KB  |  501 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12.  
  13. #include <cool/Set.h>
  14.  
  15. // CoolSet -- Simple constructor with no arguments that creates a CoolSet object
  16. //        with the minimal prime number of buckets and uses the default
  17. //        hash function.
  18. // Input: None
  19. // Output:None
  20.  
  21. template <class Type> 
  22. CoolSet<Type>::CoolSet() {
  23.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  24.   this->table = new Bucket[prime];     // Allocate buckets
  25.   this->h_function = &CoolSet_default_hash; // Setup hash 
  26.   this->compare = &CoolSet_are_keys_equal;  // Setup compare
  27. }
  28.  
  29.  
  30. // CoolSet -- Simple constructor with one argument that creates a CoolSet object
  31. //        with the minimal prime number of buckets that holds some
  32. //        user-supplied number of items and uses the default hash function
  33. // Input: Minimal number of items table must hold
  34. // Output:None
  35.  
  36. template <class Type> 
  37. CoolSet<Type>::CoolSet(unsigned long n)
  38.  : CoolBase_Hash_Table(n)
  39. {
  40.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  41.   this->table = new Bucket[prime];      // Allocate buckets
  42.   this->h_function = &CoolSet_default_hash; // Setup hash 
  43.   this->compare = &CoolSet_are_keys_equal;  // Setup compare
  44. }
  45.  
  46.  
  47. // CoolSet -- constructor that takes a reference to an existing CoolSet object and
  48. //        duplicates both its size and contents
  49. // Input: Reference to CoolSet object
  50. // Output:None
  51.  
  52. template <class Type> 
  53. CoolSet<Type>::CoolSet(const CoolSet<Type>& s)
  54.  : CoolBase_Hash_Table(s)
  55. {
  56.   long prime = hash_primes[this->current_bucket]; // Get prime number 
  57.   this->table = new Bucket[prime];     // Allocate bucksgs
  58.   for (long i = 0; i < prime; i++) {           // For each bucket count
  59.     for (int j = 0; j < s.items_in_buckets[i]; j++) // For each item in bucket
  60.       this->table[i].data[j] = s.table[i].data[j];  // Copy key/value
  61.   }
  62.   this->h_function = s.h_function;        // Use the same hash function
  63.   this->compare = s.compare;            // Use same compare function
  64. }
  65.  
  66.  
  67. // ~CoolSet -- Destructor for the CoolSet class
  68. // Input:  this*
  69. // Output: None
  70.  
  71. template <class Type> 
  72. CoolSet<Type>::~CoolSet() {
  73.   delete [] this->table;            // Free key/value storage
  74. }
  75.  
  76. // Operator== -- Determine if two hash tables are equal. This is accompilished
  77. //               by seeing that for each key/value in SeType, the same
  78. //               key/value also exists in Set2
  79. // Input:        this*, reference to second set
  80. // Output:       TRUE/FALSE
  81.  
  82. template <class Type> 
  83. Boolean CoolSet<Type>::operator== (const CoolSet<Type>& s) const {
  84.   if (this->length() != s.length())           // If not same number of entries
  85.     return FALSE;                   // Then tables are not equal
  86.   if (this->get_bucket_count() == s.get_bucket_count()) { // If same bucket cnt
  87.     for (long i = 0; i < this->get_bucket_count(); i++) { // for each bucket
  88.       int count = this->get_count_in_bucket(i);
  89.       if (count != s.get_count_in_bucket(i))    //Count eq?
  90.     return FALSE;                // No, tables !equal
  91.       Type* this_bucket = this->table[i].data;
  92.       Type* s_bucket = s.table[i].data;
  93.       for (int j = 0; j < count; j++) {        // For each item in this
  94.     for (int k = 0; k < count; k++)        // For each item in s
  95.       if ((*this->compare)(this_bucket[j], s_bucket[k]))
  96.         goto good;
  97.     return FALSE;                // Not the same, so tables !eq
  98.       good: ;
  99.       }
  100.     }
  101.   } else {
  102.     for (long i = 0; i < s.get_bucket_count (); i++)      // For each bucket
  103.       for (int j = 0; j < s.get_count_in_bucket(i); j++)  // For each item
  104.     if (!this->do_find(s.table[i].data[j]))          // If key in table
  105.       return FALSE;                   // Key not in table so different
  106.   }
  107.   return TRUE;                      // No difference, so equal
  108. }
  109.  
  110.  
  111. // do_find -- Find key/value in CoolSet
  112. // Input:  Key searching for
  113. // Output: TRUE/FALSE, current_position not updated
  114.  
  115. template <class Type> 
  116. Boolean CoolSet<Type>::do_find (const Type& key) const {
  117.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  118.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  119.   for (long i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
  120.     if (((*this->compare)(key,this->table[hash].data[i])) == TRUE)
  121.       return TRUE;                // Return success
  122.   }
  123.   return FALSE;
  124. }
  125.  
  126. // find -- Find key/value in Set
  127. // Input:  Key searching for
  128. // Output: TRUE/FALSE; current_position updated
  129.  
  130. template <class Type> 
  131. Boolean CoolSet<Type>::find (const Type& key) {
  132.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  133.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  134.   for (long i = 0; i < this->items_in_buckets[hash]; i++) { // For each entry
  135.     if (((*this->compare)(key,this->table[hash].data[i])) == TRUE){
  136.       this->curpos = SET_BUCKET_NUMBER(hash);    // Set bucket number
  137.       this->curpos |= SET_BUCKET_INDEX(i);    // Set index into bucket
  138.       this->curpos |= SET_TRAVERSED(FALSE);    // Reset traverse flag
  139.       return TRUE;                // Return success
  140.     }
  141.   }
  142.   return FALSE;
  143. }
  144.  
  145.  
  146. // value -- Return value at current position
  147. // Input:   None
  148. // Output:  Reference to value at current position
  149.  
  150. template <class Type> 
  151. Type& CoolSet<Type>::value () {
  152. #if ERROR_CHECKING
  153.   if (this->curpos == INVALID) {        // If invalid current positio
  154.     //RAISE Error, SYM(CoolSet), SYM(Invalid_Cpos)
  155.     printf ("CoolSet<%s>::value(): Invalid current position.\n", #Type);
  156.     abort ();
  157.   }
  158. #endif
  159.   if (TRAVERSED(this->curpos))            // If data in 2nd set
  160.      return this->next_data;            // Return saved value
  161.   else {
  162.     unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
  163.     long index = BUCKET_INDEX(this->curpos);          // Get Bucket index
  164.     return (this->table[hash].data[index]);          // Return value
  165.   }
  166. }
  167.  
  168.  
  169. // ***** bug? remove does not leave current position pointed at next element?
  170. // remove -- Remove element at current position from the set
  171. // Input:    this*
  172. // Output:   TRUE/FALSE
  173.  
  174. template <class Type> 
  175. Boolean CoolSet<Type>::remove () {
  176.   if (this->curpos == INVALID) {        // If valid current position
  177. #if ERROR_CHECKING
  178.     //RAISE Error, SYM(CoolSet), SYM(Invalid_Cpos)
  179.     printf ("CoolSet<%s>::remove(): Invalid current position.\n", #Type);
  180.     abort ();
  181. #endif
  182.     return FALSE;                // Return failure
  183.   }
  184.   unsigned long hash = BUCKET_NUMBER(this->curpos); // Get bucket number
  185.   long index = BUCKET_INDEX(this->curpos);        // Get index in bucket
  186.   int count = this->items_in_buckets[hash];    // Number of items in bucket
  187.   this->table[hash].data[index] = this->table[hash].data[count-1];
  188.   this->entry_count--;                // Decrement table entry count
  189.   this->items_in_buckets[hash]--;        // Decrement bucket item count
  190.   if (this->items_in_buckets[hash]) {        // If any more items in bucket
  191.     this->curpos = SET_BUCKET_NUMBER(hash);    // Save bucket number
  192.     this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]-1);
  193.     this->curpos |= SET_TRAVERSED(FALSE);    // Reset traverse flag
  194.   }
  195.   else
  196.     this->curpos = INVALID;            // Else invalidate marker
  197.   return TRUE;                    // Return success
  198. }
  199.  
  200.  
  201. // search -- Determine if one CoolSet is a subset of another
  202. // Input:    Reference to a CoolSet object
  203. // Output:   TRUE/FALSE
  204.  
  205. template <class Type> 
  206. Boolean CoolSet<Type>::search (CoolSet<Type>& s) {
  207.   if (this->length() < s.length())        // If more elements in 2nd set
  208.     return FALSE;                // Then it is not a subset
  209.   for (s.reset(); s.next(); )            // For each entry in 2nd set
  210.     if (this->find (s.value()) == FALSE)    // If not in 1st set
  211.       return FALSE;                // Then it's not a subset
  212.   return TRUE;                    // Else it's a subset
  213. }
  214.  
  215.  
  216. // put -- Hash key/value pair into table if not already there
  217. // Input: this*, key, value
  218. // Output:TRUE/FALSE
  219.  
  220. template <class Type> 
  221. Boolean CoolSet<Type>::put (const Type& key) {
  222. retry:  
  223.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  224.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  225.   if (this->items_in_buckets[hash] == BUCKET_SIZE) {       // If bucket is full
  226.     this->resize (hash_primes[this->current_bucket++]*BUCKET_SIZE);
  227.     goto retry;                    // Try again 
  228.   }
  229.   this->table[hash].data[this->items_in_buckets[hash]] = key;
  230.   this->entry_count++;                // Increment table entry count
  231.   this->curpos = SET_BUCKET_NUMBER(hash);    // Save bucket number
  232.   this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]);
  233.   this->curpos |= SET_TRAVERSED(FALSE);        // Reset traverse flag
  234.   this->items_in_buckets[hash]++;        // Increment bucket item count
  235.   return TRUE;                    // Indicate success
  236. }
  237.  
  238.  
  239. // remove -- Remove an element from the set
  240. // Input:    this*, reference to a key
  241. // Output:   TRUE/FALSE
  242.  
  243. template <class Type> 
  244. Boolean CoolSet<Type>::remove (const Type& key) {
  245.   long prime = hash_primes[this->current_bucket]; // Prime number of buckets
  246.   unsigned long hash = ((*this->h_function)(key)) % prime; // Get hash value
  247.   int count = this->items_in_buckets[hash];    // Number of items in bucket
  248.   for (int i = 0; i < count; i++) {        // For each entry in bucket
  249.     if ((*this->compare)(key,this->table[hash].data[i]) == TRUE) {
  250.       this->table[hash].data[i] = this->table[hash].data[count-1];
  251.       this->entry_count--;            // Decrement table entry count
  252.       this->items_in_buckets[hash]--;        // Decrement bucket item count
  253.       if (this->items_in_buckets[hash]) {    // If any more items in bucket
  254.     this->curpos = SET_BUCKET_NUMBER(hash); // Save bucket number
  255.     this->curpos |= SET_BUCKET_INDEX(this->items_in_buckets[hash]-1);
  256.     this->curpos |= SET_TRAVERSED(FALSE);    // Reset traverse flag
  257.       }
  258.       else
  259.     this->curpos = INVALID;            // Else invalidate marker
  260.       return TRUE;
  261.     }
  262.   }
  263.   return FALSE;                    // Return failure flag
  264. }
  265.  
  266.  
  267. // resize -- Resize a CoolSet object to hold at least some number items
  268. // Input:    this*, minimum number of items to hold
  269. // Output:   TRUE/FALSE
  270.  
  271. template <class Type> 
  272. Boolean CoolSet<Type>::resize (long n) {
  273. #if ERROR_CHECKING
  274.   if (n < 0) {                    // If invalid size specified
  275.     //RAISE (Error, SYM(CoolSet), SYM(Negative_Size)),
  276.     printf ("CoolSet<%s>::resize(): Negative resize %d.\n", #Type, n);
  277.     abort ();
  278.   }
  279. #endif
  280.   Bucket* t2;                // Temporary variable
  281.   long old_prime = hash_primes[this->current_bucket]; // Get prime number 
  282.   while (hash_primes[this->current_bucket]*BUCKET_SIZE < n) // Find prime big
  283.     this->current_bucket++;                // ... enough for number items
  284.   if (this->growth_ratio != 0.0) {        // If a growth ratio is set
  285.     long new_size = long((old_prime*BUCKET_SIZE) * (1.0 + this->growth_ratio));
  286.     if (new_size > n)
  287.       while (hash_primes[this->current_bucket]*BUCKET_SIZE < new_size)
  288.     this->current_bucket++;                // Enough size for growth ratio
  289.   }
  290.  retry:
  291.   long new_prime = hash_primes[this->current_bucket];// Get prime number 
  292.   unsigned char* t1 = new unsigned char[new_prime];  // Counts items in buckets
  293.   for (long i = 0; i < new_prime; i++)             // For each bucket count
  294.     t1[i] = 0;                         // Initialize to zero
  295.   t2 = new Bucket[new_prime];             // Allocate new buckets
  296.   for (i = 0; i < old_prime; i++) {             // For each bucket count
  297.     for (int j = 0; j < this->items_in_buckets[i]; j++) { // For each item
  298.       Type key = this->table[i].data[j];    // Get key from table
  299.       unsigned long hash = ((*this->h_function)(key)) % new_prime; // Get hash 
  300.       if (t1[hash] == BUCKET_SIZE) {        // Overflow bucket -- resize
  301.     delete [] t1;                // Delete allocated storage
  302.     delete [] t2;                // Delete allocated storage
  303.     this->current_bucket++;            // Increment bucket count
  304.     goto retry;                // Go retry again
  305.       }
  306.       t2[hash].data[t1[hash]] = key;        // Copy key into new table
  307.       t1[hash]++;                // Increment item count
  308.     }
  309.   }
  310.   delete [] this->items_in_buckets;        // Free up old storage
  311.   delete [] this->table;            // Free up old storage
  312.   this->items_in_buckets = t1;            // Point to new item count
  313.   this->table = t2;                // Point to new buckets
  314.   this->curpos = INVALID;            // Invalidate current position
  315.   return TRUE;                    // Return success
  316. }
  317.  
  318. // operator|= -- Determine the union of two sets, that is all elements in each
  319. //               set and modify the source with the result
  320. // Input:        Reference to a set
  321. // Output:       Updated CoolSet object containing union of two sets
  322.  
  323. template <class Type> 
  324. CoolSet<Type>& CoolSet<Type>::operator|= (const CoolSet<Type>& s) {
  325.   CoolSet<Type>& s2 = (CoolSet<Type>&) s;    // Locally cast away const
  326.   IterState s2_pos = s2.curpos;        // Save curpos of s
  327.   for (s2.reset (); s2.next (); )        // For each entry in 2nd set
  328.     if (this->find (s2.value()) == FALSE)     // If not in 1st set
  329.       this->put (s2.value ());            // Put to result set
  330.   s2.curpos = s2_pos;                // Put back the original curpos
  331.   this->curpos = INVALID;            // Invalidate current position
  332.   return *this;                    // Return reference
  333. }
  334.  
  335.  
  336. // operator-= -- Determine the difference of two sets, that is all elements in
  337. //               the first set that are not in the second and modify the source
  338. //               with the result
  339. // Input:        Reference to a set
  340. // Output:       Updated CoolSet object containing difference of two sets
  341.  
  342. template <class Type> 
  343. CoolSet<Type>& CoolSet<Type>::operator-= (const CoolSet<Type>& s) {
  344.   CoolSet<Type>& s2 = (CoolSet<Type>&) s;    // Locally cast away const
  345.   IterState s2_pos = s2.curpos;        // Save curpos of s
  346.   for (s2.reset (); s2.next (); )        // For each entry in 2nd set
  347.     if (this->find (s2.value()) == TRUE)     // If in 1st set
  348.       this->remove ();                // Remove from result set
  349.   s2.curpos = s2_pos;                // Put back the original curpos
  350.   this->curpos = INVALID;            // Invalidate current position
  351.   return *this;                    // Return reference
  352. }
  353.  
  354. // operator^= -- Determine the exclusive-OR of two sets, that is all elements 
  355. //               in the first set that are not in the second and all elements 
  356. //               in the second set that are not in the first and modify the
  357. //               source with the result
  358. // Input:        Reference to set
  359. // Output:       Updated CoolSet object containing XOR of two sets
  360.  
  361. template <class Type> 
  362. CoolSet<Type>& CoolSet<Type>::operator^= (const CoolSet<Type>& s) {
  363.   CoolSet<Type>& s2 = (CoolSet<Type>&) s;    // Locally cast away const
  364.   IterState s2_pos = s2.curpos;        // Save curpos of s
  365.   for (s2.reset (); s2.next (); )        // For each entry in 2nd set
  366.     if (this->find (s2.value()) == TRUE)     // If in 1st set
  367.       this->remove ();                // Remove from result set
  368.     else
  369.       this->put (s2.value());            // Else, put into result set
  370.   s2.curpos = s2_pos;                // Put back the original curpos
  371.   this->curpos = INVALID;            // Invalidate current position
  372.   return *this;                    // Return reference
  373. }
  374.  
  375.  
  376. // operator&= -- Determine the intersection of two sets, that is all elements
  377. //               that are in both sets and modify the source with the result
  378. // Input:        Reference to Set object
  379. // Output:       Updated CoolSet object containing intersection of two sets
  380.  
  381. template <class Type> 
  382. CoolSet<Type>& CoolSet<Type>::operator&= (const CoolSet<Type>& s) {
  383.   CoolSet<Type>& s2 = (CoolSet<Type>&) s;    // Locally cast away const
  384.   IterState s2_pos = s2.curpos;        // Save curpos of s
  385.   CoolSet<Type> temp(*this);            // Iterator interacts with remove
  386.   for (temp.reset(); temp.next(); )          // For each entry in 1st set
  387.     if (s2.find (temp.value()) == FALSE)      // If not in 2nd set
  388.       this->remove(temp.value());        // Remove from result set
  389.   s2.curpos = s2_pos;                // Put back the original curpos
  390.   this->curpos = INVALID;            // Invalidate current position
  391.   return *this;                    // Return reference
  392. }
  393.  
  394. // Operator= -- Assignment of one CoolSet to another duplicating size and
  395. //              contents and returning old storage
  396. // Input:       Reference to CoolSet object
  397. // Output:      Reference to new CoolSet object
  398.  
  399. template <class Type>
  400. CoolSet<Type>& CoolSet<Type>::operator= (const CoolSet<Type>& s) {
  401.   if (this != &s) {
  402.     CoolBase_Hash_Table::operator=(s);
  403.     long prime = hash_primes[this->current_bucket]; // Get prime number
  404.     delete [] this->table;                // Return old table storage
  405.     this->table = new Bucket[prime];        // Allocate bucket storage
  406.     for (long i = 0; i < prime; i++)            // For each bucket count
  407.       for (int j = 0; j < s.items_in_buckets[i]; j++) // For each item in bucket
  408.     this->table[i].data[j] = s.table[i].data[j];  // Copy key 
  409.     this->compare = s.compare;                  // Use same compare func
  410.   }
  411.   return *this;                // Return reference
  412. }
  413.  
  414.  
  415. // operator<< -- Overload the output operator to provide a crude print
  416. //               capability for CoolSet objects
  417. // Input:        ostream reference, CoolSet reference
  418. // Output:       None
  419.  
  420. template <class Type>
  421. ostream& operator<< (ostream& os, const CoolSet<Type>& s) {
  422.   os << "[ ";                    // Output opening bracket
  423.   for (int i = 0; i < s.get_bucket_count(); i++) // For each bucket
  424.     for (int j = 0; j < s.get_count_in_bucket(i); j++) // For each key/pair
  425.       os << s.table[i].data[j] << " ";         // Output the key
  426.   os << "]\n";                     // Output bracket
  427.   return os;                     // Return stream
  428. }
  429.  
  430.  
  431. // set_key_compare -- Set the compare function for this instance
  432. // Input:             Pointer to compare function
  433. // Output:            None
  434.  
  435. template <class Type> 
  436. void CoolSet<Type>::set_compare (Boolean (*cf) (const Type&, const Type&)) {
  437.   if (cf == NULL)
  438.     this->compare = &CoolSet_are_keys_equal; // Default compare
  439.   else
  440.     this->compare = cf;
  441. }
  442.  
  443. // included to define their default equality and hash functions
  444. #include <string.h>  // strcmp(const char*, const char*)
  445. #include <cool/String.h>
  446. #include <cool/Gen_String.h>
  447.  
  448. Boolean CoolSet_are_keys_equal (const CoolGen_String& v1, const CoolGen_String& v2) {
  449.    return !strcmp (v1, v2);
  450. }
  451. long CoolSet_default_hash (const CoolGen_String& key) {
  452.     return sxhash(key);
  453. }
  454.  
  455. Boolean CoolSet_are_keys_equal (const CoolString& v1, const CoolString& v2) {
  456.    return !strcmp (v1, v2);
  457. }
  458. long CoolSet_default_hash (const CoolString& key) {
  459.     return sxhash(key);
  460. }
  461.  
  462. Boolean CoolSet_are_keys_equal (char* const& v1, char* const& v2) {
  463.    return !strcmp (v1, v2);
  464. }
  465. long CoolSet_default_hash (char* const& key) {
  466.     return sxhash(key);
  467. }
  468.  
  469. // are_keys_equal -- Compares two keys using the user supplied comparison
  470. //                   function or the built-in operator== otherwise
  471. // Input:            References to two keys
  472. // Output:           TRUE/FALSE
  473.  
  474. template<class Type>
  475. Boolean CoolSet_are_keys_equal (const Type& k1, const Type& k2) {
  476.   return (k1 == k2);
  477. }
  478.  
  479.  
  480. // default_hash -- Implements the hash mechanism 
  481. // Input:          Reference to a key
  482. // Output:         Hash value (0-relative index into based table)
  483.  
  484. template<class Type>
  485. long CoolSet_default_hash (const Type& key) {
  486.   if (sizeof (key) <= 4)
  487.     return (long(key) >> 3);
  488.   else {
  489.     int hash_value = 0;
  490.     char* temp = (char*) &key;
  491.     for (int i = 0; i < sizeof (key); i++) {
  492.       hash_value = hash_value ^ temp[i];
  493.       if (hash_value < 0)
  494.     hash_value = -hash_value;
  495.     }
  496.     return (hash_value >> 3);
  497.   }
  498. }
  499.  
  500.  
  501.